package com.lun.swordtowardoffer2.c13;

import java.util.ArrayList;
import java.util.List;

public class GenerateParenthesis {

	public List<String> generateParenthesis(int num) {
		List<String> result = new ArrayList<>();
		backtracking(num, num, "", result);
		return result;
	}
	
	private void backtracking(int left, int right, String parenthesis, List<String> result) {
		if(left == 0 && right == 0) {
			result.add(parenthesis);
			return;
		}
		
		if(left > 0) {
			backtracking(left - 1, right, parenthesis + "(", result);
		}
		
		if(left < right) {
			backtracking(left, right - 1, parenthesis + ")", result);
		}
	}
	
}
